The flash memory is composed of a plurality of pages wherein 64 pages or 128 pages are defined as one block to be a storage unit of the flash memory. However, after the data are written to one page of the flash memory, the updated data cannot be over-written to the page with the previous written data. It is required to erase the block associated the written page before the later updated data are recorded in the written page. Such the manner of erasing and over-writing steps takes a lot of operation time. Thus, the updated data for the page usually are written to another physical address corresponding to the same logical address of the original page.
For example, the data of logical address “100” are stored in physical address “150” and the updated data are written to another physical address “200” when the updated data are written to the logical address “100” to replace the previous data in the same logical address “100” wherein the physical address “150” and physical address “200” are disposed in different blocks, respectively. Therefore, there are two versions of data with the logical address “100” wherein the physical address “150” is regarded as “invalid data page”. However, if the updated data corresponding to the logical address “100” are continuously written, the invalid pages with old versions are gradually increased one by one, which occupies a large amount of physical addresses. Thus, it is necessary to collect the physical addresses of the “invalid data page” in the logical address “100” for increasing the available pages of the flash memory.
The collection of the old versions of invalid data pages is termed as “garbage collection” (GC). However, when performing GC procedure, it is required to determine whether the pages in the block are valid or invalid. Conventionally, a flag is recorded in the spare area of one page if the page becomes invalid. This manner is only applicable to single-level cell (SLC) but not applicable to multi-level cell (MLC) because the MLC memory is only written once. In another conventional technique, if all the statuses of pages in the flash memory are recorded respectively as “valid” or “invalid”, it disadvantageously consumes a lot of memory for storing the statuses.
Additionally, in the application of flash memory, the mapping relationship between the logical address and physical address is limited. That is, the data with the same logical block are usually stored in the same physical block. Since the hot data, which are usually accessed, and cold data, which are seldom accessed, may be stored in the same logical block, it is necessary to scan all the pages of the physical block corresponding to the same logical block while determining whether the pages in the physical block are valid or invalid, which results in degraded efficiency of the GC procedure. Consequently, there is a need to develop a novel management method of the invalid data page for the flash memory to solve the aforementioned problems.